#include <stdio.h>
#include <stdlib.h>
#include "DoubleCircleLinkList.h"

#define true 1
#define false 0

//初始化
int DClistInit(DClist* list)
{
    list->head = NULL;
    list->tail = NULL;
    list->len = 0;
    return true ;
}

//创建节点
Node* DClistCreateNode(ElementType element)
{
    Node* NewNode = (Node*) malloc(sizeof(Node));
    if(NewNode == NULL)
    {
        printf("CreateNode malloc error!\n");
        return NULL;
    } 
    NewNode->data = element;
    NewNode->prev = NULL;
    NewNode->next = NULL;
    return NewNode;
}

//释放
void DClistDestroy(DClist* list)
{
    //空表不释放
    if(list->len == 0)
        return;

    while(list->head != list->tail)
    {
        Node* freenode = list->head;
        list->head = list->head->next;
        free(freenode);
    }
    free(list->head);
    list->head = NULL;
    list->tail = NULL;
    list->len =0;
}

//打印
void DClistPrint(DClist* list)
{
    if(list->len == 0)
        return;
    Node* cur = list->head;
    printf("next: ");
    while(cur != list->tail)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("%d ", list->tail->data);
    printf("\n");

    cur = list->tail;
    printf("prev: ");
    while(cur != list->head)
    {
        printf("%d ", cur->data);
        cur = cur->prev;
    }
    printf("%d ", list->head->data);
    printf("\n");
}

//尾插
void DClistInsertTail(DClist* list, ElementType element)
{
    Node* NewNode = DClistCreateNode(element);
    if(NewNode == NULL)
    {
        printf("InsertTail create error!\n");
        return;
    } 
    if(list->len == 0)
    {
        list->head = NewNode;
        list->tail = NewNode;
    }
    else
    {
        list->tail->next = NewNode;
        NewNode->prev = list->tail;
        list->tail = NewNode;

        //link the head and tail
        list->tail->next = list->head;
        list->head->prev = list->tail;
    }
    list->len++;   
}

//头插
void DClistInsertHead(DClist* list, ElementType element)
{
    DClistInsertTail(list, element);
    if(list->len > 1)
    {
        list->tail = list->tail->prev;
        list->head = list->head->prev;
    }
}

//尾删
void DClistPopBack(DClist* list)
{
    DClistRemoveByIndex(list, list->len - 1);
}

//头删
void DClistPopFront(DClist* list)
{
    DClistRemoveByIndex(list, 0); 
}

//按下标插入
DClist* DClistInsertByIndex(DClist* list, int index, ElementType element)
{
    //头插
    Node* NewNode = DClistCreateNode(element);
    if(index == 0)
    {
        NewNode->next = list->head;
        list->head->prev = NewNode;
        list->head = NewNode;
        NewNode->prev = list->tail;
        list->tail->next = NewNode;
        list->len++;
    }
    else
    {
        Node* cur = list->head;
        //找到要插入节点的前一个节点
        for(int i = 0; i < index - 1; ++i)
        {
            cur = cur->next;
        }
        //尾插
        if(cur->next == NULL)
        {
            list->tail->next = NewNode;
            NewNode->prev = list->tail;
            list->tail = NewNode;

            //link the head and tail
            list->tail->next = list->head;
            list->head->prev = list->tail;
            list->len++;
        }
        else
        {
            //下标位置插入
            cur->next->prev = NewNode;
            NewNode->next = cur->next;
            cur->next = NewNode;
            NewNode->prev = cur;
            list->len++;
        }
    }
    return list;
}

//按位删除
void DClistRemoveByIndex(DClist* list, int index)
{
    if(index < 0 || index > list->len)
    {
        printf("RemoveByIndex invalid space!\n");
        return;
    }
    if(index == 0)
    {
       //只有一个节点 
       if(list->len == 1)
       {
           free(list->head);
           list->head = NULL;
           list->tail = NULL;
           list->len = 0;
           return;
       }
       //删除第一个节点
       Node* freeNode = list->head;
       list->head = list->head->next;
       list->head->prev = list->tail;
       list->tail->next = list->head;
       free(freeNode);
       list->len--;
       return;
    }
    //删除最后一个节点
    if(index == list->len - 1)
    {
       Node* freeNode = list->tail;
       list->tail = list->tail->prev;
       list->tail->next = list->head;
       list->head->prev = list->tail;
       free(freeNode);
       list->len--;
       return;
    }

    Node* cur = list->head;
    while(index > 0)
    {
        cur = cur->next;
        index--;
    }
    Node* PrevNode = cur->prev;
    Node* NextNode = cur->next;
    PrevNode->next = cur->next;
    NextNode->prev = cur->prev;
    free(cur);
    list->len--;

}
//查找第一个值符合的元素
int DClistFindFirstByElement(DClist* list, ElementType element)
{
    int count = 0;
    Node* cur = list->head;
    while(cur != list->tail)
    {
        if(cur->data == element)
        {
            return count;
        }
        count++;
        cur = cur->next;
    }
    if(list->tail != NULL && list->tail->data == element)
        return count;
        
    return -1;
}
//按值删除
void DClistRemoveByElement(DClist* list, ElementType element)
{
     int index = DClistFindFirstByElement(list, element);
    while(index != -1)
    {
        DClistRemoveByIndex(list, index);
        index = DClistFindFirstByElement(list, element);
    }
}

//查找下标所对应的值
ElementType DClistFindByIndex(DClist* list, int index)
{
    if(list->len == 0)
    {
        printf("No data!\n");
    }
    Node* cur = list->head;
    for(int i = 0; i < index; ++i)
    {
        cur = cur->next;
    }
    return cur->data;
}

//通过下标设定值
void DClistSetValueByIndex(DClist* list, int index, ElementType element)
{
    Node* cur = list->head;
    for(int i = 0; i < index; ++i)
    {
        cur = cur->next;
    }
    cur->data = element;
}

//更改元素值
void DClistSetValueByElement(DClist* list, ElementType oldValue, ElementType newValue)
{
    Node* cur = list->head;
    for(int i = 0; i < list->len; ++i)
    {
        if(cur->data == oldValue)
        {
            cur->data = newValue;
        }
        cur = cur->next;
    }
}

